Chmury

Limit pamięci: 64 MB

Na niebie znajduje się chmur. Wszystkie chmury poruszają się w tym samym kierunku ze stałą, jednakową prędkością, równą . To oznacza, że dla każdej liczby całkowitej , punkt chmury w chwili znajduje się w punkcie o współrzędnych .

Wszystkie chmury są reprezentowane przez wielokąty zawierające swoje obrzeża, których wierzchołki mają całkowitoliczbowe współrzędne. Wielokąt reprezentujący chmurę nie musi być wypukły, ale żadne jego krawędzie nie przecinają się (jedynymi punktami wspólnymi mogą być końce kolejnych krawędzi). Chmury mogą nachodzić na siebie.

Na ziemi, w punkcie o współrzędnych , znajduje się centrum kontroli lotów kosmicznych. Bezpośrednio nad centrum, ponad chmurami, umieszczony jest satelita geostacjonarny, który komunikuje się z centrum lotów przy pomocy wiązki laserowej. Wiązka ta jest skierowana pionowo w górę. Gdy wiązka lasera przecina chmurę, łączność pomiędzy centrum a satelitą zostaje zerwana. Nawet jeśli laser przecina pojedynczy wierzchołek chmury, komunikacja nie jest możliwa. W chwili początkowej laser nie przecina żadnej chmury. Twoim zadaniem jest napisanie programu, który obliczy, ile razy komunikacja zostaje przerwana do chwili, gdy wszystkie chmury "odpłyną" w siną dal.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opisy chmur oraz współrzędne wektora wiatru,
• obliczy, ile razy komunikacja zostanie przerwana,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite , i , pooddzielane pojedynczymi odstępami, , ; jest liczbą chmur, jest wektorem reprezentującym prędkość i kierunek poruszania się chmur (). Współrzędna x odpowiada kierunkowi wschód-zachód, natomiast współrzędna y - północ-południe.

Kolejne wierszy zawiera opisy chmur, każda chmura w osobnym wierszu. Każdy z tych wierszy zawiera ciąg liczb całkowitych, pooddzielanych pojedynczymi odstępami. Pierwsza liczba, , to liczba wierzchołków chmury, . Kolejne liczb (; ) to współrzędne kolejnych wierzchołków chmury podanych w kolejności zgodnej z ruchem wskazówek zegara.

Wiązka lasera przecina krawędzie chmur nie więcej niż razy.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę całkowitą, oznaczającą, ile razy komunikacja została przerwana.

Przykład

Dla danych wejściowych:

4 -2 -1
4 6 2 6 4 8 4 8 2
4 2 3 1 -1 2 5 4 2
3 -3 1 -1 2 -1 -1
5 5 3 3 3 3 5 6 5 6 -1

poprawną odpowiedzią jest:

3

Rysunek powyżej przedstawia chmury widziane z góry. Przerywana linia reprezentuje miejsca na niebie, które przetnie wiązka lasera.

Autor zadania: Jakub Radoszewski.